package com.ttx.algorithm.leetcode.traversal;

import java.util.LinkedList;
import java.util.Queue;

/**
 * https://leetcode-cn.com/problems/number-of-islands/
 * 200 岛屿数量  <br>
 *
 * <p>
 *     给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。
 *     一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。
 *     你可以假设网格的四个边均被水包围。
 *
 *    输入:
 *    11000
 *    11000
 *    00100
 *    00011
 *
 *    输出: 3
 *
 * </p>
 *
 * @author TimFruit
 * @date 19-10-1 下午11:12
 */
public class P200NumberOfIslands {

    public int numIslands(char[][] grid) {


        int rows=grid.length;
        if(rows==0){
            return 0;
        }
        int len=grid[0].length;

        int num=0;//岛屿个数
        int[][] marks=new int[rows][len]; //标记岛屿


        for(int i=0;i<rows;i++){
            for(int j=0;j<len;j++){

                if(marks[i][j]>0){ //已标记为岛屿
                    continue;
                }
                if(grid[i][j]=='0'){
                    continue;
                }

                // grid[i][j]== '1', 发现新岛屿
                num++;
                //遍历标记新岛屿
                markIsland(grid, marks, i, j, num);

            }


        }



        return num;
    }



    private void markIsland(char[][] grid, int[][] marks, int si, int sj, int markNum){
        int rows=grid.length;
        int len=grid[0].length;


        Queue<Point> queue=new LinkedList<Point>();
        Point point=new Point(si, sj);
        queue.add(point);

        int i,j;
        while(!queue.isEmpty()){
            point=queue.poll();

            i=point.i;
            j=point.j;
            if(marks[i][j]>0 || grid[i][j]=='0'){ //已被标记或者是水
                continue;
            }

            marks[i][j]=markNum; //标记

            //上
            if(i-1>=0 && grid[i-1][j]=='1' && marks[i-1][j]==0){
                queue.add(new Point(i-1, j));
            }

            //下
            if(i+1<rows && grid[i+1][j]=='1' && marks[i+1][j]==0){
                queue.add(new Point(i+1, j));
            }

            //左
            if(j-1>=0 && grid[i][j-1]=='1' && marks[i][j-1]==0){
                queue.add(new Point(i, j-1));
            }

            //右
            if(j+1<len && grid[i][j+1]=='1' && marks[i][j+1]==0){
                queue.add(new Point(i, j+1));
            }

        }


    }



    class Point{
        int i;
        int j;

        public Point(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }


}
